package com.yun.algorithmproblem.leetcode;

import java.util.*;

public class Leetcode1091 {
    //BFS
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1) {
            return -1;
        }
        int n = grid.length;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        dist[0][0] = 1;
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int x = arr[0], y = arr[1];
            if (x == n - 1 && y == n - 1) {
                return dist[x][y];
            }
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    if (x + dx < 0 || x + dx >= n || y + dy < 0 || y + dy >= n) {
                        continue;
                    }
                    if (grid[x + dx][y + dy] == 1 || dist[x + dx][y + dy] <= dist[x][y] + 1) {
                        continue;
                    }
                    dist[x + dx][y + dy] = dist[x][y] + 1;
                    queue.offer(new int[]{x + dx, y + dy});
                }
            }
        }
        return -1;
    }

    //A*算法
    //int[][] dist=new int[]{i,j,g(n),f(n)}

    int n = 0;
    int[] dx = {1, 1, 1, 0, 0, -1, -1, -1};
    int[] dy = {1, 0, -1, 1, -1, 1, 0, -1};

    public int shortestPathBinaryMatrix1(int[][] grid) {
        n = grid.length;
        if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) {
            return -1;
        }
        if (n == 1) {
            return 1;
        }
        PriorityQueue<Node> heap = new PriorityQueue<>(10, Comparator.comparingInt(o -> o.fn));
        grid[0][0] = 1;
        heap.offer(new Node(0, 0, 1));
        while (!heap.isEmpty()) {
            Node curr = heap.poll();
            int x = curr.x, y = curr.y;
            if (x == n - 1 && y == n - 1) {
                return grid[x][y];
            }
            for (int j = 0; j < 8; j++) {
                int newX = x + dx[j], newY = y + dy[j];
                if (newX < 0 || newX > n - 1 || newY < 0 || newY > n - 1) {
                    continue;
                }
                if (grid[newX][newY] == 0 || grid[newX][newY] > grid[x][y] + 1) {
                    grid[newX][newY] = grid[x][y] + 1;
                    heap.offer(new Node(newX, newY, grid[newX][newY]));
                }
            }
        }
        return -1;
    }

    public class Node {
        int x;
        int y;
        int fn;

        public Node(int x, int y, int gn) {
            this.x = x;
            this.y = y;
            this.fn = distance(x, y, gn);
        }

        public int distance(int x, int y, int gn) {
            return gn + n - 1 - Math.min(x, y);
        }
    }
}
